package leetcode_400;

import java.util.Stack;

/**
 *@author 周杨
 *DecodeString_394 反解码一个字符串
 *describe:用栈 AC 100%
 *2018年7月15日 下午5:34:57
 */
public class DecodeString_394 {
	/**
	 * describe:解法错误 没有预料到"3[a2[c]]"这种嵌套用例
	 * 2018年7月15日 下午3:24:04
	 */
	public String decodeString1(String s) {
		StringBuilder res=new StringBuilder();
        int index=0;
        while(index<s.length()) {
        	StringBuilder intS=new StringBuilder();
        	while(s.charAt(index)!='[') {
        		intS.append(s.charAt(index));
        		++index;
        	}
        	++index;
        	StringBuilder stringS=new StringBuilder();
        	while(s.charAt(index)!=']') {
        		stringS.append(s.charAt(index));
        		++index;
        	}
        	for(int i=0;i<Integer.valueOf(intS.toString());++i)
        		res.append(stringS);
        	++index;
        }


	   return res.toString();
    }
	
	/**
	 * describe:用两个栈 AC 100%
	 * 2018年7月15日 下午5:34:35
	 */
	public String decodeString(String s) {
		 String res = "";
	        Stack<String> charStack = new Stack<>();
	        Stack<Integer> numStack = new Stack<>();
	        char sArray[] = s.toCharArray();
	        for(int i = 0 ; i < s.length(); i++){
	           if(sArray[i] > '0' && sArray[i] <= '9'){  // if num = 10,111... while
	               int j = i;
	               int count = 0;
	               while(sArray[j] >= '0' && sArray[j] <= '9'){ //考虑大于1位数的情况
	                   count = count * 10 +  sArray[j] - '0';
	                   j++;
	               }
	               i = j - 1;
	               numStack.push(count);
	           } 
	           else if(sArray[i] == '['){
	               charStack.push(res);
	               res = "";
	           }
	           else if(sArray[i] == ']'){
	               StringBuilder temp = new StringBuilder(charStack.pop());
	               int count = numStack.pop();
	               while(count > 0){
	                   temp.append(res);
	                   count--;
	               }
	               res = temp.toString();
	           }
	           else
	             res += sArray[i];
	        }
	        return res;
	}
}
